Efficient data compression to reduce the data volume significantly decreases both data communication and archive costs. Among existing data compression algorithms, Vector Quantization (VQ) has been demonstrated to be an effective method capable of producing good reconstructed data quality at high compression ratios. The primary advantage of the VQ algorithm, as compared to other high compression ratio algorithms such as the adaptive transform coding algorithm, is its extremely simple decoding procedure, which makes it a great potential technique for the single-encoder, multiple-decoder data compression systems.
The VQ algorithm has been selected as the data compression algorithm to be used for rapid electronic transfer of browse image data from an on-line archive system to end users of the Alaska SAR Facility (ASF) and the Shuttle Imaging Radar C (SIR-C) ground data systems. For this on-line archive application, VQ is required to reduce the volume of browse image data by a factor of 15 to 1 so that the data can be rapidly transferred through the Space Physics Analysis Network (SPAN) having a 9600 bits per second data rate, and be accurately reconstructed at the sites of scientific users.
Another application of the VQ algorithm is the real-time downlink of the Earth Observing System (EOS) on-board processor data to the ground data users. For this data downlink application, VQ is required to reduce the volume of image data produced by the on-board processor by a factor of 7 to 1 so that the data can be transferred at real-time through the direct downlink channel limited at 1 Megabits per second data rate. These flight projects are currently undertaken by the National Aeronautics and Space Administration (NASA) for imaging and monitoring of global environmental changes.
Aside from these space applications, VQ can also be applied to a broad area in commercial industry for data communication and archival applications, such as digital speech coding over telephone lines, High Definition TV (HDTV) video image coding and medical image coding.
Vector quantization is a generalization of scalar quantization. In vector quantization, the input data is divided into many small data blocks (i.e., data vectors). The quantization levels (i.e., codevectors) are vectors of the same dimension as the input data vectors. A general functional block diagram for vector quantization is shown in FIG. 1. A codebook 10 comprised of codevectors C.sub.0, C.sub.1, . . . , C.sub.N-1, is used at the transmit end of a communication channel 11 for data encoding and a duplicate codebook 10' is used at the receive end for data decoding. An encoding functional block 12 carries out the algorithm indicated by ##EQU1## where: x.sup.[k] represents the input data vector at time k; C.sub.i is the codevector; D(x.sup.[k], C.sub.i) is the distortion function; N the total number of codevectors; and i.sup.[k] the optimal codevector index. The procedure defined by that equation is to select the stored codevector which yields the minimum distortion between an input data vector x.sup.[k] and the stored codevectors C.sub.0, C.sub.1 . . . , C.sub.N-1. The optimal index i.sup.[k] transmitted through the channel 11 is used at the receive end for the decoding function in block 13 carried out by using the index i.sup.[k] to look up the codevector C.sub.i.spsb.[k] in the codebook 10' that is then used as the reconstructed data vector x.sup.[k], which closely approximates the original data vector x.sup.[k]. The decoding procedure can be expressed as EQU x.sup.[k] =C.sub.i.spsb.[k] ( 2)
which is a table look-up procedure. Data compression is achieved since fewer bits are needed to represent the codevector indices than the input data vectors.
The codebook is generated by training a subset of the source data. The performance of the codebook is highly dependent on the similarity between the training data and the coded data. It then follows that the encoding procedure need only involve computing the distortion between each input data vector and all of the stored codevectors to select the best match. This algorithm is known as the full-searched VQ algorithm.
The major drawback of the full-searched VQ algorithm is the high complexity involved in drawing up (training) the codebook and then data encoding, which poses a great challenge for real-time application. To reduce the encoding complexity, the tree-searched VQ algorithm is employed such that the complexity only grows linearly rather than exponentially as the codebook size increases. For the tree-searched VQ, the codebook is divided into several tree levels, as illustrated in FIG. 2 for a 2-level tree-structured codebook. In the encoding process, the input data x.sup.[k] is first compared with the first level codebook C.sub.0,C.sub.1, . . . C.sub.N.sbsb.1.sub.-1. Based on the selected codevector, the input data x.sup.[k] vector is then compared with the codevectors of the corresponding second level subcodebook C.sub.0,0,C.sub.0,1 . . . C.sub.N.sbsb.1.sub.-1,.sub.N.sbsb.2.sub.-1. This encoding procedure is repeated until the input data vector is compared with the last level subcodebook. The best matched codevector at the last level subcodebook is then used to represent this input data vector.